/*
 *  SableJBDD, a Java Binary Decision Diagram package.
 *  Copyright (C) 2003  Feng Qian
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */
//$Id: Prime.java,v 1.3 2004/03/15 02:07:08 fqian Exp $
package SableJBDD.bdd.internal;

/**
 * A class finds the smallest prime number above a given number
 *
 * This is a standard example from Sun's developer's forum. However,
 * the algorithm itself is simple enough.
 *
 * @author Feng Qian
 */
public class Prime {
  /**
   * Finds the smallest prime number greater than or equal to a given integer.
   * @param n a given integer
   * @return the smallest prime number greater than or equal to n
   */
  public static int getSmallestPrimeGTE(int n) {
    while (!isPrime(n)) n++;
    return n;
  }

  /**
   * @return true if a given number is a prime number
   */
  public static boolean isPrime(int n) {
    if (n <= 2) return n==2;
    if (n % 2 == 0) return false;
    for (int i=3, end = (int)Math.sqrt(n); i<=end; i+=2) {
      if (n % i == 0) return false;
    }
    return true;
  }
}
